Communication systems, and particularly cellular communication systems, are well known. Cellular communication systems, as is known, consist of individual cell sites, each equipped to communicate with mobile communication units located within the cell site. Communication in a cell site is conducted over a communication resource, often referred to as a communication channel, which may consist of a pair of radio frequencies which are used by the mobile communication unit to transmit and receive information with the cell site transceiver. Several of the communication resources may be dedicated to particular functions such as two-way transmission of control information. The total number of communication resources, however, is limited.
In planning cellular radiotelephone systems there is a never ending tension among maximizing system capacity, providing Carrier-to-Interferer (C/I) immunity, meeting cell-to-cell hand-off topography, and etc. This is due primarily to the scarce radio spectrum available, i.e., the scarce number of communication channels. To increase capacity, the limited number of communication resources are repeatedly reused at different cell sites throughout the cellular communication system. However, higher resource reuse adversely affects C/I and may not be possible because of hand-off criteria. Thus the system operator is left with the very difficult task of allocating resources to the cells in the most efficient way possible. This task, however, is very labor intensive. Once resources are allocated within a system, tuning of the system to reduce the effects of interfering resources or adding/removing resources from cells to balance capacity is often not performed even though system performance suggests that it should be.
The present methods of assigning frequencies (channels) to the cell sites of a cellular system are generally manual. Prearranged groups of frequencies are typically assigned to cells which are laid out in a specific reuse pattern (typically a grid of evenly packed hex cell sites). This method assumes that the cell sites will be installed "on grid" from the planning process. Unfortunately, many constraints such as expensive real estate, infeasible antenna locations, zoning ordinances, etc. prevent the cellular operator from obtaining rights to install the cell sites at these "on-grid" locations. Not having cell sites installed on the grid causes many interference problems when attempting to use normal frequency reuse patterns. This is due to the fact that many reused and adjacent channels are installed at cell sites which are no longer "on grid" with one another (e.g. too close) and thus interfere with one another. Propagation tools are used to examine specific areas of the system to determine if there will be any potential problems with channel reuse or adjacent channel usage between pairs of cells. For difficult terrain areas (mountains, water, heavy building density), grid-based frequency planning is difficult due to radio frequency (RF) propagation problems.
The reuse frequency planning method uses sets of predefined groups of frequencies for each reusing sector or cell site in the reuse pattern. There are different frequency groups for each type of reuse pattern. For example, there are typically 14 voice channels in each of 24 subgroups for the Advanced Mobile Phone Service (AMPS) 4--sector reuse pattern. An entire subgroup of voice channels is typically allotted (reserved) for each sector or cell site. If only 8 channels are required in a specific site, then the extra channels are either reserved (wasting the resource), or the subgroup is splintered into fractional groups and is reused elsewhere.
The frequency planning process is a very time consuming process. Typically a set of assignments are made on paper, and then RF propagation estimates are made to determine if there will be any problems between reusing/adjacent channels. If problems are detected, then the human planner backtracks undoing some of the channel assignments, and redoing them with new channel assignments. This iterative process continues until an acceptable plan is achieved. For a typical system such as Las Vegas, this process may take 3-4 weeks from scratch.
It has been proposed to utilize automated methods to provide for communication resource allocation. For example, in the commonly assigned U.S. patent application Ser. No. 08/322,046 filed Oct. 12, 1994 entitled "Method of Allocating Communication Resources in a Communication System" by Allan Shedlo, a method providing for channel tuning in a cellular system allocated channels is taught. The method utilizes reiterative techniques for altering the channel allocation of a cellular system based upon a predefined set of allocation criteria.
There has also been suggested by Anton, Kunz and Ruber in their paper "CHANNEL ASSIGNMENT USING SIMULATED ANNEALING", a method of channel allocation utilizing the technique known as simulated annealing. Simulated annealing is, as it is titled, characterized as a simulation of the annealing process which occurs in nature to achieve a system minimum. Several draw backs of applying these simulated annealing techniques to channel assignment include unacceptable convergence times and lack of 100 percent channel assignment.
Therefore, a need exists for a method of allocating and reallocating communication resources to cells of a communication system which accounts for the various criteria which must be satisfied within the system without consuming an inordinate amount of time and resources. Such a method must further permit 100 percent channel assignment while concomitantly reducing channel interference and co-channel and adjacent channel reuse at hand-off candidate cells.